#include <iostream>

template<class K>
struct BSTreeNode
{
public:
  BSTreeNode(const K& key)
  :_left(nullptr)
  ,_right(nullptr)
  ,_key(key)
  {}
  BSTreeNode<K>* _left;
  BSTreeNode<K>* _right;
  K _key;
};

template<class K>
class BSTree
{
public:
  typedef BSTreeNode<K> Node;
  BSTree()=default;
  BSTree(const BSTree<K>& T)
  {
    _root=_CopyTree(T._root);
  }
  ~BSTree()
  {
    _DestroyTree(_root);
    _root=nullptr;
  }

  BSTree<K>& operator=(BSTree<K> T)
  {
    std::swap(_root,T._root);
    return *this;
  }



public:
  bool Insert(const K& key)
  {
    if(_root==nullptr)
    {
      _root=new Node(key);
      return true;
    }
    Node* parent=nullptr;
    Node* cur=_root;
    while(cur)
    {
      if(key<cur->_key)
      {
        parent=cur;
        cur=cur->_left;
      }
      else if(key>cur->_key)
      {
        parent=cur;
        cur=cur->_right;
      }
      else
      { 
       return false;
      }
    }

    //cur为空，开始插入节点
    cur=new Node(key);
    if(key<parent->_key)
    {
      parent->_left=cur;
    }
    else 
    {
      parent->_right=cur;
    }
    return true;
  }

  bool Erase(const K& key)
  {
    Node* parent=nullptr;
    Node* cur=_root;//如果要删除_root呢?
    while(cur)
    {
      if(key<cur->_key)
      {
        parent=cur;
        cur=cur->_left;
      }
      else if(key>cur->_key)
      {
        parent=cur;
        cur=cur->_right;
      }
      else 
      {
        //找到了要删除的节点
        //1.节点左为空，则父节点指向其右 2.否则，如果节点右为空，父节点指向其左
        if(!cur->_left)
        {
          if(parent==nullptr)
          {
            _root=cur->_right;
          }
          else if(parent->_left==cur)
          {
            parent->_left=cur->_right;
          }
          else 
            parent->_right=cur->_right;

          delete cur;
        }
        else if(!cur->_right)
        {
          if(parent==nullptr)
          {
            _root=cur->_left;
          }
          else if(parent->_left==cur)
          {
            parent->_left=cur->_left;
          }
          else 
            parent->_right=cur->_left;

          delete cur;
        }
        else 
        {
          //左右孩子都不为空
          Node* minParent=cur;
          Node* minRight=cur->_right;
          while(minRight->_left)
          {
            minParent=minRight;
            minRight=minRight->_left;
          }
          //minRight替换法
          cur->_key=minRight->_key;
          //删除minRight,minRight左一定为空
          if(minParent->_right==minRight)
          {
            minParent->_right=minRight->_right;
          }
          else 
            minParent->_left=minRight->_right;
          
          delete minRight;

        }

        return true;
      }
    }
    //没有要删除的节点
    return false;
  }

  void DestroyTree()
  {
    _DestroyTree(_root);
    _root=nullptr;
  }


  bool FindK(const K& key)
  {
    Node* cur=_root;
    while(cur)
    {
      if(key<cur->_key)
      {
        cur=cur->_left;
      }
      else if(key>cur->_key)
      {
        cur=cur->_right;
      }
      else 
      {
        return true;
      }
    }
    return false;
  }

  void InOrder()
  {
    _InOrder(_root);
    std::cout<<std::endl;
  }

  //--------------------------------------
  //递归版本实现1.InsertR 2.EraseR 3.FindKR
  bool InsertR(const K& key)
  {
    return _InsertR(_root,key);
  }

  bool FindKR(const K& key)
  {
    return _FindKR(_root,key);
  }

  bool EraseR(const K& key)
  {
    return _EraseR(_root,key);
  }
private:
  bool _InsertR(Node*& root,const K& key)
  {
    if(root==nullptr)
    {
      root=new Node(key);
      return true;
    }

    if(key<root->_key)
    {
      return _InsertR(root->_left,key);
    }
    else if(key>root->_key)
    {
      return _InsertR(root->_right,key);
    }
    else 
      return false;
  }

  bool _FindKR(Node* root,const K& key)
  {
    if(root==nullptr)
      return false;
    if(key<root->_key)
      return _FindKR(root->_left,key);
    else if(key>root->_key)
      return _FindKR(root->_right,key);
    else 
      return true;
  }

  bool _EraseR(Node*& root,const K& key)
  {
    if(root==nullptr)
      return false;

    if(key<root->_key)
      return _EraseR(root->_left,key);
    else if(key>root->_key)
      return _EraseR(root->_right,key);
    else 
    {
      //找到了要删除的节点,root此时含有父节点的链接关系
      //1.左为空，root连接到其有 2.右为空，root链接到其左 
      Node* del=root;
      if(root->_left==nullptr)
      {
        root=root->_right;
      }
      else if(root->_right==nullptr)
      {
        root=root->_left;
      }
      else 
      {
        //3.左右都为空，替换法
        Node* minRight=root->_right;
        while(minRight->_left)
        {
          minRight=minRight->_left;
        }
        //找到了替换节点
        std::swap(root->_key,minRight->_key);
        //转换成情况1或2，继续递归
        return _EraseR(root->_right,key);
      }

        delete del;
        return true;
    }
  }

  Node* _CopyTree(Node* root)
  {
    if(root==nullptr)
    {
      return nullptr;
    }

    Node* dest=new Node(root->_key);
    dest->_left=_CopyTree(root->_left);
    dest->_right=_CopyTree(root->_right);
    return dest;
  }

  void _DestroyTree(Node* root)
  {
    if(root==nullptr)
      return;
    
    _DestroyTree(root->_left);
    _DestroyTree(root->_right);
    delete root;
  }

  void _InOrder(Node* root)
  {
    if(root==nullptr)
      return;

    _InOrder(root->_left);
    std::cout<<root->_key<<" ";
    _InOrder(root->_right);
  }

  Node* _root=nullptr;
};



